#include "train.h"


class UnionSet {
public:
	UnionSet(int n) : fa(n + 1), Size(n + 1) {
		for (int i = 0; i <= n; i++) {
			fa[i] = i;
			Size[i] = 1;
		}
	}
	int find(int x) {
		return fa[x] = (fa[x] == x ? x : find(fa[x]));
	}
	int merge(int a, int b) {
		int aa = find(a), bb = find(b);
		if (aa == bb) return 0;
		if (Size[aa] < Size[bb])
		{
			fa[aa] = bb;
			Size[bb] += Size[aa];
		}
		else
		{
			fa[bb] = aa;
			Size[aa] += Size[bb];
		}
		return 1;
	}
	vector<int> fa, Size;
};

class Solution {
public:
	int longestConsecutive(vector<int>& nums) {
		int n = nums.size();
		int cnt = 0; //记录用到多少号下标
		unordered_map<int, int> h; //判断重复数字
		UnionSet u(n);
		for (int i = 0; i < n; i++)
		{
			int x = nums[i];
			if (h.find(x) != h.end()) continue; //如果x可以在h找到，就停止，排除重复数字
			if (h.find(x + 1) != h.end()) u.merge(h[x],h[x + 1]);
			if (h.find(x - 1) != h.end()) u.merge(h[x], h[x - 1]);
		}
		int ans = 0;
		for (int i = 0; i < cnt; i++)
		{
			ans = max(ans, u.Size[i]);
		}
		return ans;
	}
};